package listnode.question;

import listnode.ListNode;

/**
 * 题目:
    给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。
 * 示例:
    输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3
    输出：Intersected at '8'

 * 注意:
    交点不是数值相等，而是指针相等,即地址也要相等。

 * 思路:
    1.目当一个人走到自己链表的尽头时，就换到另一个链表的起点继续走
    2.当另一个人走到自己链表的尽头时，也换到另一个链表的起点继续走
    3.这样两人最终会走相同的总路程（A链表长度 + B链表长度）
      必定同时到达：因为总路程相同，所以：
      如果有交点，会在第二次经过交点时相遇
      如果没有交点，会同时到达终点(null)
      跳到另一个链表"是为了平衡长度差
 */


public class GetIntersectionNode {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        // p1 指向 A 链表头结点，p2 指向 B 链表头结点
        ListNode p1 = headA, p2 = headB;
        while (p1 != p2) {
            // p1 走一步，如果走到 A 链表末尾，转到 B 链表
            if (p1 == null) p1 = headB;
            else            p1 = p1.next;
            // p2 走一步，如果走到 B 链表末尾，转到 A 链表
            if (p2 == null) p2 = headA;
            else            p2 = p2.next;
        }
        return p1;
    }
}
